package Hot100.Medium.Backtracking;

/**
 * LC79 单词搜索
 */
public class LC79_SearchWordInArray {
    public static void main(String[] args) {
        LC79_SearchWordInArray solver = new LC79_SearchWordInArray();

        char[][] board = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };

        String word = "ABCCED";

        boolean result = solver.exist(board, word);
        System.out.println("是否存在单词 \"" + word + "\" : " + result);
    }


    public boolean exist(char[][] board, String word){
        boolean[][] visited = new boolean[board.length][board[0].length];
        //遍历二维数组，每一个位置都作为起点进行dfs
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, word, i, j, 0, visited)){
                    return true;
                }
            }
        }
        return false;
    }

    //递归实现四个方向的dfs
    public boolean dfs(char[][] board, String word, int i, int j, int index, boolean[][] visited){
        if(index == word.length()){
            return true;
        }
        // 剪枝操作，当i，j越界时，剪枝。当visited[i][j]为true时，证明刚才选中了这个字母，也就是路径已经走过，因此剪枝。最后就是当目前选中的字母不是对应的字母时，剪枝。
        if(i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1 || visited[i][j] || board[i][j] != word.charAt(index)){
            return false;
        }
        visited[i][j] = true;
        // 向四个方向继续搜索
        boolean found = dfs(board, word, i - 1, j, index + 1, visited) ||
                dfs(board, word, i + 1, j, index + 1, visited) ||
                dfs(board, word, i, j - 1, index + 1, visited) ||
                dfs(board, word, i, j + 1, index + 1, visited);
        visited[i][j] = false;// 回溯防止递归搜索时，正确的路径被标记导致漏搜
        return found;
    }

}
